Signal processing algorithms are typically executed by a computer system to enhance or otherwise change one or more aspects of a signal. For example, signal processing algorithms can be executed by a processor of a computer to denoise, fill, etc. various portions of the signal. These signal processing algorithms can generally include generating one or more values for a reference patch in the signal using a plurality of collected patches that neighbor that reference patch. However, to date, conventional signal processing algorithms have required a tradeoff between computational intensiveness and reduced signal quality.
In one implementation, the signal may be a digital image, in which case a signal processing algorithm may be employed to enhance or otherwise change one or more aspects of a digital image. For example, a signal processing algorithm operating on the image can be executed by the processor of a computer to denoise, fill, deblur, re-color, etc. portions of the image as desired. The above mentioned tradeoff between computational intensiveness and reduced image quality is still required. It should be noted that the computational intensiveness of the algorithm generally increases with the number of dimensions of the signal, thus finding a compromise is even more important for signals with a high number of dimensions. For example, one class of well known signal processing algorithms, primarily used for denoising purposes, includes non-local algorithms, such as Non-Local Means (NLM), Non-Local-Bayes, block-matching and 3D filtering (BM3D), etc. With respect to non-local algorithms, neighbor patches are collected and processed (e.g. averaged) as mentioned above.
Just by way of example, NLM involves, for each reference patch, processing a high number of other (i.e. neighboring) patches to denoise it. In particular, for each reference patch, a weighted sum of the neighbor patches is used to get an estimate for the denoised reference patch. Because of the high number of patches required, NLM is computationally intensive. The computational burden in some implementations of NLM and other non-local algorithms is reduced by only considering, for the reference patch, a limited number of neighboring patches collected through a nearest neighbor (NN) approach. However, the nearest neighbors to a reference patch may have noise correlated with the noise in the reference patch, as a result of the neighbors collection strategy and/or because of correlations introduced by preprocessing of the signal (e.g., demosacing in a color image). As a consequence, any value generated for the reference patch from those neighbors can still be affected by an undesired level of noise, and the noise in the reference patch will not be cancelled as is otherwise desired. When other applications (i.e. other than denoising) are considered, the presence of correlated noise between the reference and neighbor patches may also lead to the introduction of artifacts. Thus, while using NN in NLM can reduce the computational burden of the traditional implementation of NLM, using NN also reduces the quality of the image. Another well known signal processing algorithm that can similarly use NN includes bilateral filtering, which is a special case of the class of non-local algorithms where a size of each patch is a 1×1 pixel, and the weights in the bilateral filter kernel play the role of the weighting patches in NLM.
Thus, there is a need for addressing these issues and/or other issues associated with the prior art.